/*
 * @Author: 缄默
 * @Date: 2021-12-12 21:46:41
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-12 22:10:00
 */

//字符串的交错组成

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool isCross1(string s1, string s2, string aim);

int main() {
    string s1 = "abc";
    string s2 = "123";
    string aim = "abc123";
    cout << isCross1(s1, s2, aim) << endl;

    return 0;
}

bool isCross1(string s1, string s2, string aim) {
    if (s1.size() == 0 || s2.size() == 0 || aim.size() == 0) return false;
    if (aim.size() != s1.size() + s2.size()) return false;
    int row = s1.size() + 1;
    int col = s2.size() + 1;
    //dp矩阵
    vector<vector<bool>> dp(row, vector<bool>(col));
    //初始化dp矩阵
    dp[0][0] = true;
    //判断s1和aim的前i项是否相等
    for (int i = 1; i < row; i++) {
        dp[i][0] = s1[i - 1] == aim[i - 1] && dp[i - 1][0];
    }
    //判断s2的是否相等
    for (int j = 1; j < col; j++) {
        dp[0][j] = s2[j - 1] == aim[j - 1] && dp[0][j - 1];
    }

    //dp矩阵求真，找出动态转移方程    
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = (dp[i - 1][j] && s1[i - 1] == aim[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == aim[i + j - 1]);
        }
    }
    //返回值
    return dp[row - 1][col  -1];
}
